/**
 * 
 */
package No301_400.No371_380.KthSmallestElementinaSortedMatrix_378;
/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月4日 下午4:22:31 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {
//	public static int kthSmallest(int[][] matrix, int k) {
//		
//	}
	
	/*
	 * 自己写的，虽然没超时但是时间太长
	 * */
    public static int kthSmallest(int[][] matrix, int k) {
        int col = matrix[0].length;
        int row = matrix.length;
        int[] a = new int[k+1];
        int nowSize = 0;
        int fnum = col*row;
        for(int x = 0;x < fnum;x++){
        	int temp = matrix[x/col][x%col];
        	int i = nowSize - 1;
        	for (; i >= 0; i--) {
				if(temp < a[i]){
					a[i+1] = a[i];
				}
				else {
					break;
				}
			}
        	a[i+1] = temp;
			if(nowSize < k){
				nowSize++;
			}
        }
        return a[k-1];
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] a = {{1,5,9},{10,11,13},{12,13,15}};
		int[][] a1 = {{1,2},{1,3}};
		System.out.println(kthSmallest(a1,2));
	}

}
